/**
 * Created with Intellij IDEA.
 * Description:
 * User: 28318
 * Date: 2025-11-08
 * Time: 17:14
 */
public class MyDoubleLinkedList implements IDoubleLinkedList {

    LinkedNode head;
    LinkedNode Last;
    int usedSize;

    public static class LinkedNode{
        int val;
        LinkedNode prev;
        LinkedNode next;

        public LinkedNode(){

        }

        public LinkedNode(int val) {
            this.val = val;
        }
    }

//    头插法
    @Override
    public void addFirst(int data) {
        LinkedNode newN = new LinkedNode(data);
        this.usedSize++;
        if (this.head == null){
            this.head = newN;
            this.Last = newN;
            return;
        }
        this.head.prev = newN;
        newN.next = this.head;
        this.head = newN;
    }

//    尾插法
    @Override
    public void addLast(int data) {
        if (this.Last == null){
            addFirst(data);
            return;
        }
        LinkedNode newN = new LinkedNode(data);
        newN.prev = this.Last;
        this.Last.next = newN;
        this.Last = newN;
        this.usedSize++;
    }

//    在index下标位置插入
    @Override
    public boolean addIndex(int index, int data) {
        if (!this.checkIndex(index)){
            return false;
        }
        if (index == 0){
            this.addFirst(data);
            return true;
        }
        if (index == this.usedSize){
            this.addLast(data);
            return true;
        }
        LinkedNode cur = this.head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        LinkedNode newN = new LinkedNode(data);
        cur.prev.next = newN;
        newN.prev = cur.prev;
        cur.prev = newN;
        newN.next = cur;
        this.usedSize++;
        return true;
    }

//    链表中是否存在key值
    @Override
    public boolean contains(int key) {
        if (this.head == null){
            return false;
        }
        LinkedNode cur = this.head;
        while (cur != null){
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

//    删除第一个值为key的节点
    @Override
    public void remove(int key) {
        if (!this.contains(key)){
            return;
        }
        LinkedNode cur = this.head;
        if (cur.val == key){
            this.head = this.head.next;
            this.usedSize--;
            return;
        }
        while (cur != null && cur.val != key){
            cur = cur.next;
        }
        if (cur == null){
            return;
        }
        if (cur.next == null){
            cur.prev.next = null;
            this.usedSize--;
            return;
        }
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        this.usedSize--;
    }

//    删除所有值为key的节点
    @Override
    public void removeAllKey(int key) {
        if (!this.contains(key)){
            return;
        }
        while (this.head.val == key && this.head.next != null){
            this.head.next.prev = null;
            this.head = this.head.next;
            this.usedSize--;
        }
        if (this.head.next == null && this.head.val == key){
            this.head = null;
            this.Last = null;
            this.usedSize--;
            return;
        }
        LinkedNode cur = this.head;
        while (cur != null){
            if (cur.val == key){
                if (cur.next == null){
                    cur.prev.next = null;
                    this.usedSize--;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    this.usedSize--;
                }
            }
            cur = cur.next;
        }
    }

//    获取链表长度
    @Override
    public int size() {
        return this.usedSize;
    }

//    打印链表
    @Override
    public void display() {
        System.out.print("[ ");
        if (this.head == null){
            System.out.println("]");
            return;
        }
        LinkedNode cur = this.head;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println("]");
    }

//    清空链表
    @Override
    public void clear() {
        if (this.head == null){
            return;
        }
        LinkedNode cur = this.head;
        LinkedNode curN = cur.next;
        while (cur != null){
            curN = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curN;
        }
        this.head = null;
        this.Last = null;
        this.usedSize = 0;
    }

//    检查index的合法性
    public boolean checkIndex(int index){
        if (index < 0 | index > this.usedSize){
            return false;
        }
        return true;
    }
}
